package com.lzhsite.leetcode.algoritom.practise;

import java.util.Stack;

public class 求最大子矩阵 {

	public int getMatrixMaxSum(int matrix[][]) {

		int arr[] = new int[matrix.length];

		Integer maxSum = 0;
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix[i].length; j++) {
				arr[j] = (matrix[i][j] > 0 ? 0 : arr[j] + 1);
			}
			maxSum = Math.max(maxSum, getArrMaxSum(arr));
		}

		return 0;
	}

	private int getArrMaxSum(int[] arr) {
		// TODO Auto-generated method stub

		Stack<Integer> stack = new Stack();
		Integer j = null;
		Integer k = -1;
		int max = 0;
		for (int i = 0; i < arr.length; i++) {

			k = stack.peek();
			while (!stack.isEmpty() && arr[k] >= arr[i]) {
				j =  stack.pop();
				k = stack.peek();
				max = Math.max(max, ((i - 1) - (k + 1) + 1) * arr[j]);
			}
			stack.push(i);
		}
		while (stack.isEmpty()) {
			j = stack.pop();
			k = stack.isEmpty() ? -1 : stack.peek();
			max = Math.max(max, ((arr.length - 1) - (k + 1) + 1) * arr[j]);
		}

		return max;
	}
	
	
	
	
	

	public static void main(String[] args) {
		int matrix[][] = { { 1, 1, 1, 1, 1 }, { 1, 1, 1, 1, 1 }, { 1, 1, 1, 1, 1 }, { 1, 1, 1, 1, 1 } };

		System.out.println(matrix.length + " " + matrix[0].length);
	}
}
